package datastructure.trie;

import java.util.TreeMap;

/**
 * @author XY
 * @version 1.0
 * @date 2021/12/23 15:51
 * @Description
 */
public class Leet211 {

    class WordDictionary {

        private class Node{
            //标识该节点是否是一个字符串的结尾
            public boolean isWord;
            //用map直接标识下一个节点的值，和指向的下一个节点
            public TreeMap<Character, Node> next;

            public Node(){
                this(false);
            }

            public Node(boolean isWord){
                this.isWord=isWord;
                next = new TreeMap<>();
            }
        }

        private Node root;

        public WordDictionary() {
            root = new Node();
        }

        public void addWord(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                //如果不进入if则说明当前字符已经存在
                if(cur.next.get(c)==null){
                    cur.next.put(c,new Node());
                }
                cur = cur.next.get(c);
            }
            //先判断当前单词之前不是一个完整的单词的时候才进行操作
            cur.isWord = true;
        }

        //如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
        public boolean search(String word) {
            return match(root,word,0);
        }

        private boolean match(Node node,String word,int index){
            if(index == word.length()){
                return node.isWord;
            }
            char c = word.charAt(index);
            if(c != '.'){
                if(node.next.get(c)==null){
                    return false;
                }
                return match(node.next.get(c),word,index+1);
            }else{
                //如果是. 那么下一个所有分支的字符都能进行匹配
                for (Character character : node.next.keySet()) {
                    //对所有分支再次进行往下查找，如果有一个分支找到了当前字符，就返回true
                    if(match(node.next.get(character),word,index+1)){
                        return true;
                    }
                }
                return false;
            }
        }
    }

}
